#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int output[100] = {0};
bool flag = false;

void checkout(int data[], int size){
	for(int i = 0; i < size; i++){
		printf("%d%s", data[i], i==size-1?"":" ");
	}
	printf("\n");
}

bool isEqual(int a[], int b[], int N){
	for(int i = 0; i < N; i++){
		if(a[i] != b[i]){
			return false;
		}
	}
	return true;
}

void InsertSort(int data[], int size){
	for(int i = 0; i < size; i++){
		if(flag){
			checkout(data, size);
			return;
		}
		if(isEqual(data, output, size)){
			printf("Insertion Sort\n");
			flag = true;
		}
		int temp = data[i];
		for(int j = i; j >= 0; j--){
			if(data[j] > temp){
				data[j+1] = data[j];
				if(data[j] != temp){
					data[j] = temp;
				}
			}
		}
	}
}

int compare(const void* a, const void* b){
	return *(int*)a - *(int*)b;
}

void mergeSort(int data[], int N){
	for(int i = 1; i < N; i++){
		if(flag){
			checkout(data, N);
			return;
		}
		if(isEqual(data, output, N)){
			printf("Merge Sort\n");
			flag = true;
		}
		for(int j = 0, next = i; j < N; j += i*2, next += i*2){
			if(next > N - 1){ next = N - 1; }
			qsort(data+j, next-j+1, 4, compare);
		}
	}
}

int main(){
	int N = 0;
	int input[100] = {0};
	int temp[100] = {0};
	int i = 0;
	scanf("%d", &N);
	//输入原始数据
	for(i = 0; i < N; i++){
		scanf("%d", &input[i]);
	}
	//输入中间排序数组
	for(i = 0; i < N; i++){
		scanf("%d", &output[i]);
	}
	//复制一份原始数据
	for(i = 0; i < N; i++){
		temp[i] = input[i];
	}
	InsertSort(temp, N);
	if(!flag){
		mergeSort(input, N);
	}
	return 0;
}
